#include "main/utils.h"
using namespace std;

// **********solution1************
int minCostCore1(const vector<int>& nums, int index) {
  if (index < 2) {
    return nums[index];
  }
  return min(minCostCore1(nums, index - 1), minCostCore1(nums, index - 2)) + nums[index];
}

int minCost1(const vector<int>& nums) {
  return min(minCostCore1(nums, nums.size() - 1), minCostCore1(nums, nums.size() - 2));
}

// **********solution2************
void helper2(const vector<int>& nums, int idx, vector<int>& dp) {
  if (idx < 2) {
    dp[idx] = nums[idx];
  } else if (dp[idx] == 0) {
    helper2(nums, idx - 1, dp);
    helper2(nums, idx - 2, dp);
    dp[idx] = min(dp[idx - 1], dp[idx - 2]) + nums[idx];
  }
}

int minCost2(const vector<int>& nums) {
  int size = nums.size();
  vector<int> dp(size, 0);
  helper2(nums, size - 1, dp);
  return min(dp[size - 1], dp[size - 2]);
}

// **********solution3************
int minCost3(const vector<int>& nums) {
  int size = nums.size();
  vector<int> dp;
  for (int i = 0; i < size; ++i) {
    if (i < 2) {
      dp.push_back(nums[i]);
    } else {
      int tmp = min(dp[i - 1], dp[i - 2]) + nums[i];
      dp.push_back(tmp);
    }
  }
  return min(dp[size - 1], dp[size - 2]);
}

// **********solution4************
int minCost4(const vector<int>& nums) {
  int size = nums.size();
  vector<int> dp = {nums[0], nums[1]};
  for (int i = 2; i < size; ++i) {
    dp[i % 2] = min(dp[0], dp[1]) + nums[i];
  }
  return min(dp[0], dp[1]);
}

int main() {
  vector<int> nums = {1, 100, 1, 1, 100, 1};
  cout << minCost1(nums) << endl;
  cout << minCost2(nums) << endl;
  cout << minCost3(nums) << endl;
  cout << minCost4(nums) << endl;

  return 0;
}
